package com.unimod.fsml.model;

import java.text.MessageFormat;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

import com.evelopers.common.exception.SystemException;
import com.evelopers.unimod.analysis.FormulaResolver;
import com.evelopers.unimod.core.stateworks.Action;
import com.evelopers.unimod.core.stateworks.Event;
import com.evelopers.unimod.core.stateworks.Guard;
import com.evelopers.unimod.core.stateworks.State;
import com.evelopers.unimod.core.stateworks.StateMachine;
import com.evelopers.unimod.core.stateworks.StateType;
import com.evelopers.unimod.core.stateworks.Transition;
import com.evelopers.unimod.parser.ExprParser;
import com.evelopers.unimod.parser.Infix;

/**
 * <p>
 * Implemets unhandled tokens resolving algorithm.
 * </p>
 * <p>
 * {@link com.evelopers.unimod.core.stateworks.StateMachine StateMachine} passed 
 * to {@link #resolve resolve} method represents parser that accepts only possible
 * strings. The goal of the algorithm is to add additional transitions to 
 * the state machine to make each state to handle every event (i.e. token).
 * </p>
 * <p>
 * New transitions are of two types. 
 * <ul>
 *   <li>
 *   Transitions of the first type based on consideration that some tokens 
 *   were omitted in the input stream. So to handle unexpected token 
 *   the nearest state handling the token should be found. If found state
 *   handles token it has appropriate transition(s). New transition has the 
 * 	 same trigger event and target as the transitions of found state.  
 *   </li>
 *   <li>
 *   The second type transitions just skipping unexpected tokens.
 *   </li>  
 * </p>      
 * @author mmazin
 * @author Ivan Lagunov
 */
public class UnhandledTokensResolver {
    private static final Log logger = LogFactory.getLog(UnhandledTokensResolver.class);

    public static final String ERROR_TRANSITION_NAME = "error";
	public static final int INFINITY = Integer.MAX_VALUE / 3;

	public static final String REMOVE_TOKENS_ACTION = "o5.z1";
	public static final String ADD_TOKENS_ACTION = "o5.z2";

	private static final MessageFormat REMOVE_TOKENS_CONDITION = new MessageFormat("o2.x1 <= {0}"); 
	private static final MessageFormat ADD_TOKENS_CONDITION = new MessageFormat("o2.x1 >= {0}"); 
	
	private static UnhandledTokensResolver unhandledTokensResolver;
	
	private List<State> states;
	private Map<Event, List<State>> eventToHandlingState = new HashMap<Event, List<State>>();
	
	private UnhandledTokensResolver() {
	}
	
	public static UnhandledTokensResolver getInstance() {
		if (null == unhandledTokensResolver) {
			unhandledTokensResolver = new UnhandledTokensResolver();
		}
		return unhandledTokensResolver;
	}
	
	public void resolve(StateMachine machine) throws SystemException {
		buildStates(machine);		
		buildEventToHandlingState();
//		dumpMap();
		
		for (Object o : machine.getAllStates()) {
			State state = (State) o;
			if (isStable(state)) {
				resolve(machine, state);
			}
		}
	}

	/**
	 * Fills list {@link #states} with list of stable 
	 * states of <code>machine</code>.
	 */
	private void buildStates(StateMachine machine) {
		states = new LinkedList<State>();
		for (Object o : machine.getAllStates()) {
			State state = (State) o;
			if (isStable(state)) {
				states.add(state);
			}
		}
	}
	
	/**
	 * Fills map {@link #eventToHandlingState}. Key in this
	 * map is event, value is list of stable states that have
	 * outgoing transition triggered the event that is key. 
	 */
	private void buildEventToHandlingState() {
		for (State state : states) {
			for (State cur = state; cur != null; cur = cur.getSuperstate()) {
				for (Object o : cur.getEvents(true)) {
					Event event = (Event) o;
					List<State> handlingStates;
					if (eventToHandlingState.containsKey(event)) {
						handlingStates = eventToHandlingState.get(event);
					} else {
						handlingStates = new LinkedList<State>();
						eventToHandlingState.put(event, handlingStates);
					}
					handlingStates.add(state);
				}
			}
		}
	}

	private void resolve(StateMachine machine, State state) throws SystemException {
		for (Event event : eventToHandlingState.keySet()) {
			// Ignore ANY event
			if (event.equals(Event.ANY)) {
			    continue;
			}
			
			// Get list of states handling the event
			List<State> handlingStates = eventToHandlingState.get(event);
			
			// If the state doesn't handle the event 
			if (!handlingStates.contains(state)) {
				LinkedList<Transition> pathToHandlingState = getPathToHandlingState(state, event, new HashSet<State>());

				// If state handling the event is attainable from the state 
				if (pathToHandlingState != null) {
					Transition transition = pathToHandlingState.getLast();
					State handlingState = transition.getTargetState();

					// Build list of transitions outgoing from the 
					//  handlingState and triggered on the event 
					List<Transition> apprTransitions = new LinkedList<Transition>();
					for (State cur = handlingState; cur != null; cur = cur.getSuperstate()) {
						for (Object o : cur.getFilteredOutgoingTransitions(event, false)) {
							Transition outgoingTransition = (Transition) o;
							apprTransitions.add(outgoingTransition);
						}
					}
					
					for (Transition template : apprTransitions) {
						createAddTokenTransition(machine, state, template, pathToHandlingState);
					}
				}
				
				createRemoveTokenTransition(machine, state, event, getNumberOfTokensToAdd(pathToHandlingState));
			}
		}
	}
	
	/**
	 * <p>
	 * Builds and returns the shortest path from the given 
	 * sourceState to the state handling given event.
	 * </p> 
	 * @return The list of transitions making the path to
	 * the state handling the event. If no such state is found
	 * then returns <code>null</code>.
	 */
	public LinkedList<Transition> getPathToHandlingState(State sourceState, Event event, Set<State> visitedStates) {
		if (visitedStates.contains(sourceState)) {
			return null;
		} else {
			visitedStates.add(sourceState);
		}

		LinkedList<Transition> pathToHandlingState = null;
		
		for (State curState = sourceState; curState != null; curState = curState.getSuperstate()) {
			for (Object o : curState.getOutgoingTransitions()) {
				Transition transition = (Transition) o;
				if (ERROR_TRANSITION_NAME.equals(transition.getName())) {
					continue;
				}
				State targetState = transition.getTargetState();
				
				// If target state handles the event then the 
				//   transition is the shortest path because
				//   it has length one or zero (if current state 
				//   is initial). It is assumed that sourceState				
				//   isn't handling state.   
				if ((eventToHandlingState.get(event)).contains(targetState)) {
					pathToHandlingState = new LinkedList<Transition>();
					pathToHandlingState.add(transition);
					return pathToHandlingState; 
				}
				
				LinkedList<Transition> newPath = getPathToHandlingState(targetState, event, visitedStates);
				if (newPath != null) {
					newPath.addFirst(transition);
					if (pathToHandlingState == null || getNumberOfTokensToAdd(newPath) < getNumberOfTokensToAdd(pathToHandlingState)) {
						pathToHandlingState = newPath;
					}
				}
			}
		}

		return pathToHandlingState;
	}

	private void createAddTokenTransition(StateMachine machine, State sourceState, Transition template, List<Transition> pathToHandlingState) throws SystemException {
		// Create condition: 
		//   [template.Guard AND numberOfUnconsumableTokens >= numberOfTokensToAdd]
		//   It means that tokens are added iff it is more profitable 
		//   then to remove redundant. 
		int numberOfTokensToAdd = getNumberOfTokensToAdd(pathToHandlingState); 
		Guard guard = machine.createGuard(
                Infix.infix(FormulaResolver.and(
                        template.getGuard().getAST(), 
                        ExprParser.parse(ADD_TOKENS_CONDITION.format(new Object[] {
                                new Integer(numberOfTokensToAdd)}), machine, null))));

		Transition transition = machine.createTransition(
				sourceState, 
				template.getTargetState(), 
				guard, 
				template.getEvent());
		
		// Mark transition as erroneous
		transition.setName(ERROR_TRANSITION_NAME);

		// Add add tokens logging action
		Action action = machine.createAction(ADD_TOKENS_ACTION);
		transition.addOutputAction(action);

		// Add actions from all transitions and states in the path
		for (Transition transitionInPath : pathToHandlingState) {
			for (Object o : transitionInPath.getOutputActions()) {
				Action a = (Action) o;
				transition.addOutputAction(a);
			}
			for (Object o : transitionInPath.getTargetState().getOnEnterActions()) {
				Action a = (Action) o;
				transition.addOutputAction(a);
			}
		}
		for (Object o : template.getOutputActions()) {
			Action a = (Action) o;
			transition.addOutputAction(a);
		}

	}

	private void createRemoveTokenTransition(StateMachine machine, State sourceState, Event event, int numberOfTokensToAdd) {
		Guard guard = numberOfTokensToAdd < INFINITY ? 
				machine.createGuard(REMOVE_TOKENS_CONDITION.format(new Object[] {new Integer(numberOfTokensToAdd)})) : 
				Guard.TRUE;
		Action action = machine.createAction(REMOVE_TOKENS_ACTION);
		Transition transition = machine.createTransition(sourceState, sourceState, guard, event);
		transition.setName(ERROR_TRANSITION_NAME);
		transition.addOutputAction(action);
	}

	/**
	 * Returns number of transitions triggered by event, i.e.
	 * transitions from initial state aren't count. 
	 */
	private int getNumberOfTokensToAdd(List<Transition> transitions) {
		if (transitions == null) {
			return INFINITY;
		}
		int number = 0;
		for (Transition transition : transitions) {
			if (!StateType.INITIAL.equals(transition.getSourceState().getType())) {
				number++;
			}
		}
		return number;		
	}
	
	private boolean isStable(State state) {
		return !state.isComposite() && !StateType.INITIAL.equals(state.getType());
	}

    
/*	private State getStableTarget(Transition transition) {
		State target = transition.getTargetState();
		while (true) {
			if (target.isComposite()) {
				target = target.getInitialSubstate();
				continue;
			}
			if (StateType.INITIAL.equals(target.getType())) {
				target = (State) ((Transition) target.getOutgoingTransitions().get(0)).getTargetState();
				continue;
			}
			break;
		}
		return target;
	}
*/
	protected void dumpMap() {
		for (Event event : eventToHandlingState.keySet()) {
			logger.debug(event.getName() + " handled by " + eventToHandlingState.get(event));
		}
	}
}
